By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 35, Issue 1, pp. 1-257

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

Some 3CNF Properties Are Hard to Test

Eli Ben-Sasson, Prahladh Harsha, and Sofya Raskhodnikova

pp. 1-21

BibTeX  Abstract Full Text:  PDF

A Probabilistic Analysis of Trie-Based Sorting of Large Collections of Line Segments in Spatial Databases

Michael Lindenbaum, Hanan Samet, and Gisli R. Hjaltason

pp. 22-58

BibTeX  Abstract Full Text:  PDF

Holographic Proofs and Derandomization

Dieter van Melkebeek and Rahul Santhanam

pp. 59-90

BibTeX  Abstract Full Text:  PDF

Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time

Artur Czumaj, Funda Ergün, Lance Fortnow, Avner Magen, Ilan Newman, Ronitt Rubinfeld, and Christian Sohler

pp. 91-109

BibTeX  Abstract Full Text:  PDF

Polynomial Time Approximation Schemes for MAX-BISECTION on Planar and Geometric Graphs

Klaus Jansen, Marek Karpinski, Andrzej Lingas, and Eike Seidel

pp. 110-119

BibTeX  Abstract Full Text:  PDF

Minimum-Weight Spanning Tree Construction in O(log log n) Communication Rounds

Zvi Lotker, Boaz Patt-Shamir, Elan Pavlov, and David Peleg

pp. 120-131

BibTeX  Abstract Full Text:  PDF

The Complexity of Approximating the Entropy

Tugkan Batu, Sanjoy Dasgupta, Ravi Kumar, and Ronitt Rubinfeld

pp. 132-150

BibTeX  Abstract Full Text:  PDF

Well-Separated Pair Decomposition for the Unit-Disk Graph Metric and Its Applications

Jie Gao and Li Zhang

pp. 151-169

BibTeX  Abstract Full Text:  PDF

A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem

Greg Kuperberg

pp. 170-188

BibTeX  Abstract Full Text:  PDF

A Better-Than-Greedy Approximation Algorithm for the Minimum Set Cover Problem

Refael Hassin and Asaf Levin

pp. 189-200

BibTeX  Abstract Full Text:  PDF

A Superpolynomial Lower Bound for a Circuit Computing the Clique Function with at most (1/6)log log n Negation Gates

Kazuyuki Amano and Akira Maruoka

pp. 201-216

BibTeX  Abstract Full Text:  PDF

Bounds on the Efficiency of Generic Cryptographic Constructions

Rosario Gennaro, Yael Gertner, Jonathan Katz, and Luca Trevisan

pp. 217-246

BibTeX  Abstract Full Text:  PDF

Approximating k-node Connected Subgraphs via Critical Graphs

Guy Kortsarz and Zeev Nutov

pp. 247-257

BibTeX  Abstract Full Text:  PDF